package 算法.leetcode.labuladong.二叉树;

import 算法.leetcode.offer.base.TreeNode;

/**
 * @author lchenglong
 * @date 2022/6/23
 */
public class 二叉树的直径 {
    class Solution {
        // 利用全局变量计算,记录所有子树中可能的最大子树
        int ans;
        // 直径 = 左子树深度 + 右子树深度
        public int diameterOfBinaryTree(TreeNode root) {
            maxDepth(root);
            return ans;
        }

        public int maxDepth(TreeNode root){
            if (root == null) return 0;
            // 遍历左右子树
            int lm = maxDepth(root.left);
            int rm = maxDepth(root.right);
            // 计算每个子树的最大直径
            ans = Math.max(ans,lm + rm );
            return Math.max(lm,rm) +1;
        }

    }
}
